/*
  Copyright (c) DataStax, Inc.

  Licensed under the Apache License, Version 2.0 (the "License");
  you may not use this file except in compliance with the License.
  You may obtain a copy of the License at

  http://www.apache.org/licenses/LICENSE-2.0

  Unless required by applicable law or agreed to in writing, software
  distributed under the License is distributed on an "AS IS" BASIS,
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  See the License for the specific language governing permissions and
  limitations under the License.
*/

#include <gtest/gtest.h>

#include "random.hpp"
#include "third_party/hdr_histogram/hdr_histogram.hpp"
#include "vector.hpp"

using namespace datastax::internal;

// 626 of the first numbers generated with the default seed of 5489LL using boost::mt19937_64
uint64_t random_numbers[] = {
  14514284786278117030ULL, 4620546740167642908ULL,  13109570281517897720ULL,
  17462938647148434322ULL, 355488278567739596ULL,   7469126240319926998ULL,
  4635995468481642529ULL,  418970542659199878ULL,   9604170989252516556ULL,
  6358044926049913402ULL,  5058016125798318033ULL,  10349215569089701407ULL,
  2583272014892537200ULL,  10032373690199166667ULL, 9627645531742285868ULL,
  15810285301089087632ULL, 9219209713614924562ULL,  7736011505917826031ULL,
  13729552270962724157ULL, 4596340717661012313ULL,  4413874586873285858ULL,
  5904155143473820934ULL,  16795776195466785825ULL, 3040631852046752166ULL,
  4529279813148173111ULL,  3658352497551999605ULL,  13205889818278417278ULL,
  17853215078830450730ULL, 14193508720503142180ULL, 1488787817663097441ULL,
  8484116316263611556ULL,  4745643133208116498ULL,  14333959900198994173ULL,
  10770733876927207790ULL, 17529942701849009476ULL, 8081518017574486547ULL,
  5945178879512507902ULL,  9821139136195250096ULL,  4728986788662773602ULL,
  840062144447779464ULL,   9315169977352719788ULL,  12843335216705846126ULL,
  1682692516156909696ULL,  16733405176195045732ULL, 570275675392078508ULL,
  2804578118555336986ULL,  18105853946332827420ULL, 11444576169427052165ULL,
  5511269538150904327ULL,  6665263661402689669ULL,  8872308438533970361ULL,
  5494304472256329401ULL,  5260777597240341458ULL,  17048363385688465216ULL,
  11601203342555724204ULL, 13927871433293278342ULL, 13168989862813642697ULL,
  13332527631701716084ULL, 1288265801825883165ULL,  8980511589347843149ULL,
  1639193574298669424ULL,  14012553476551396225ULL, 7818048564976445173ULL,
  11012385938523194722ULL, 1594098091654903511ULL,  5035242355473277827ULL,
  11507220397369885600ULL, 4097669440061230013ULL,  4158775797243890311ULL,
  8008476757622511610ULL,  18212599999684195413ULL, 3892070972454396029ULL,
  15739033291548026583ULL, 5240984520368774617ULL,  15428220128146522508ULL,
  6764778500174078837ULL,  17250425930626079997ULL, 15862445320841941901ULL,
  9055707723866709616ULL,  407278260229756649ULL,   6679883267401891436ULL,
  13585010976506536654ULL, 9580697194899010248ULL,  7802093638911637786ULL,
  535562807229422763ULL,   16772549087470588412ULL, 2069348082463192648ULL,
  18080878539236249869ULL, 12688200000096479737ULL, 8989665349769173357ULL,
  13575112928849473200ULL, 10859033464356012248ULL, 9748216112997718693ULL,
  8405158063935141693ULL,  15279502632583570477ULL, 16055899490125284200ULL,
  9066388900883848980ULL,  17884680971936629565ULL, 16395391805201036549ULL,
  2550532686790805254ULL,  8052938288948613298ULL,  6344035301348514175ULL,
  2193824757648316037ULL,  10113332896580941759ULL, 14001553499759966766ULL,
  597702890888347204ULL,   1874324574384293454ULL,  10826913572691111562ULL,
  12821185545071087721ULL, 14606566723149387105ULL, 15679487422249894303ULL,
  16146086267469614290ULL, 11169330698794304272ULL, 17590151747242102595ULL,
  18278229723818623796ULL, 15994633360516603469ULL, 11881756471423721131ULL,
  11153906733009525059ULL, 16836145075420168747ULL, 8614597919830747987ULL,
  1459907787369619658ULL,  16682004712721580156ULL, 15261848763679157527ULL,
  2717413695111288049ULL,  14889665525641206303ULL, 12338480473037317818ULL,
  2557597240994564872ULL,  12402353581130313583ULL, 15355546302939095474ULL,
  17651033590338072704ULL, 11616809212196625943ULL, 6561978461173088746ULL,
  5962436378610109024ULL,  1168012300494473422ULL,  5175053317267933097ULL,
  4740525681678845797ULL,  1614376253554691208ULL,  1358027693590031708ULL,
  1856992378370522222ULL,  2410813678132517023ULL,  11582456654366157909ULL,
  5754940895753314317ULL,  17548218371729667895ULL, 17945642044770404276ULL,
  3721164045489467070ULL,  13394551493150992827ULL, 12475264300415171883ULL,
  10462606688633056562ULL, 13251365510693735175ULL, 3876338822302790600ULL,
  13771801863059799470ULL, 13815564444636394855ULL, 16495110748802246170ULL,
  2156091871580385249ULL,  12069080176326280986ULL, 489805578737239572ULL,
  5271183164515543116ULL,  11286401144444756863ULL, 6746000579485080744ULL,
  5186625150343537151ULL,  13119883039086991857ULL, 16025170396082521338ULL,
  2259331576759215945ULL,  16362343102415556603ULL, 10982898132796723193ULL,
  14666888772828547003ULL, 10462483830193419334ULL, 18236154274104239589ULL,
  17759599582309981676ULL, 9339512652453242670ULL,  14635458573977612405ULL,
  13273192362623128494ULL, 7419053614262815071ULL,  2139880725825605974ULL,
  15336265650071823816ULL, 6291952205449675957ULL,  14977329074317573394ULL,
  4364768269648744391ULL,  17232241565077788317ULL, 8450549923677533764ULL,
  15732483035355013039ULL, 13831185231495622915ULL, 6819123640184841760ULL,
  11886944798543888851ULL, 10879889186777890996ULL, 15555433551230813341ULL,
  105259452319848079ULL,   3441909642659419332ULL,  5480947869602487239ULL,
  6247709904124292706ULL,  13391610271247915041ULL, 18346462037123761313ULL,
  16636317150577797347ULL, 14149179703416851896ULL, 2376171948756359367ULL,
  5152472389910152792ULL,  2368047066677070121ULL,  16396163399604156946ULL,
  14864288050288048653ULL, 7393398358587456124ULL,  9728143941576351989ULL,
  5481913815176021747ULL,  16927964714362701213ULL, 14993236783745363262ULL,
  9552302871570670457ULL,  11071069341174528295ULL, 15381321939083200837ULL,
  8816171210895558106ULL,  6071991122052964372ULL,  10925078611503375837ULL,
  15239629154712277871ULL, 8615167154188153180ULL,  4917230293625512515ULL,
  14895742215835130464ULL, 2359753755290725009ULL,  6783321469015983851ULL,
  360705462143558065ULL,   2287732638733919300ULL,  2984153050512747353ULL,
  8021412450653308816ULL,  12759258587083258672ULL, 1585563973173997547ULL,
  18209504305389149669ULL, 11416757620121532143ULL, 6846989578536141166ULL,
  4365862612957164362ULL,  2931876801952518067ULL,  680191398818283694ULL,
  1834352496547951770ULL,  12616538556720116808ULL, 17563613795929063197ULL,
  14519515363534791688ULL, 4349527158980778739ULL,  6714794984698083967ULL,
  6696141578113299617ULL,  17231874453010340947ULL, 18425812703539835928ULL,
  3707544366662920973ULL,  10197276740411893574ULL, 12864434420502416888ULL,
  12767250491273234520ULL, 1588549204908870909ULL,  6610295429674120152ULL,
  5281895767268096036ULL,  1739897672032589486ULL,  17406469206626426854ULL,
  8710378533013875691ULL,  9587926405039941516ULL,  2805299725371867574ULL,
  7146901261023555807ULL,  1825062423171923931ULL,  3049052876249887095ULL,
  10771741767689142181ULL, 8733642741329011601ULL,  11979515434717210935ULL,
  10043245691272652957ULL, 5830279975302858953ULL,  17190113074333440499ULL,
  18260575806620923460ULL, 14335648769917655401ULL, 4153816861017702156ULL,
  14590500750979768984ULL, 810991542442466488ULL,   7089785717813579612ULL,
  12357837562747114001ULL, 5554121432788679660ULL,  5931025703748246718ULL,
  2097835176693352889ULL,  12745618408404359587ULL, 6090924568528767236ULL,
  14734637834598564704ULL, 14439652293742648615ULL, 132405348116615733ULL,
  13869945305505934743ULL, 7372953811704808036ULL,  7756437368369298361ULL,
  3794582695199039623ULL,  12917619229835701974ULL, 14320084076906478671ULL,
  2606626751703588462ULL,  3137561743724131360ULL,  13808802441028589896ULL,
  14231944027275971054ULL, 16852581317945783254ULL, 10323673491841952054ULL,
  2313335010769237820ULL,  13955532667350441768ULL, 5747153089934705338ULL,
  13377135145695875091ULL, 6830230899286657495ULL,  81856298782858401ULL,
  1754724887913860152ULL,  13750479713795882912ULL, 11120120136303124367ULL,
  15046307382468953177ULL, 3696979254055818020ULL,  15352898388246644384ULL,
  1024778962410818770ULL,  2388728043318081123ULL,  6871857727931721608ULL,
  17721619206096294273ULL, 10585202864517959301ULL, 10898249199547365704ULL,
  9663430180652362739ULL,  1737102419936989910ULL,  5117227310201589790ULL,
  16884367896390523102ULL, 10498150099412419335ULL, 1921007855220546564ULL,
  7643484074408755248ULL,  11318429053286342939ULL, 1370093900783164344ULL,
  6776537281339823025ULL,  3450492372588984223ULL,  9401014545757436331ULL,
  7896519943553875907ULL,  14303443932332314010ULL, 281238069833157985ULL,
  9628364435514671685ULL,  1035647896705322917ULL,  940113500519447970ULL,
  12858978713386075837ULL, 2103046007104782505ULL,  1170332608028903179ULL,
  6569179731999105361ULL,  9795365446060253382ULL,  3663276878692063340ULL,
  11746321300354091749ULL, 5408361990473950532ULL,  9735653452670998906ULL,
  4324195634733601175ULL,  9037136744494003310ULL,  10715330324656609711ULL,
  3474343689175121886ULL,  5794004792094061662ULL,  13295581273946061060ULL,
  7292949743142825837ULL,  10886028626057941279ULL, 10688849249577735178ULL,
  17297010345160851373ULL, 13658139148821214513ULL, 4468290234101910565ULL,
  9583516840381960864ULL,  2100818272677130469ULL,  3835407486618772476ULL,
  11687972045781987867ULL, 2584265809482868424ULL,  2184370854727222683ULL,
  17762352308671769689ULL, 10901114407297935135ULL, 17932666452350314317ULL,
  14800534017102555607ULL, 16233839909626358812ULL, 1704089397092793640ULL,
  2891239861334407450ULL,  18077585692287687954ULL, 2363047449739120434ULL,
  5904357530901606076ULL,  16765772907460692007ULL, 8757786729323486734ULL,
  3706883612695347371ULL,  14958907430930711064ULL, 9624134580897548276ULL,
  10298009507777483067ULL, 5667412839234900228ULL,  6828701555684071915ULL,
  10482797977665945217ULL, 13440894740881464138ULL, 12078258924098889769ULL,
  5740761565098658841ULL,  13914375003115830180ULL, 16808960379045776034ULL,
  18421450170384511575ULL, 16478974619417516521ULL, 14381565232287562804ULL,
  12792472782420522791ULL, 6620422687983566193ULL,  12025299949416885293ULL,
  6046334025019123ULL,     16769051888439418536ULL, 10312203372653850423ULL,
  720028297035890629ULL,   6441255456466558203ULL,  9874005816230679263ULL,
  15903170012916142038ULL, 7557768652767625223ULL,  17626605079857371651ULL,
  9092603716684679963ULL,  15518831173015579794ULL, 300798272301981904ULL,
  13762040857722893585ULL, 3117104080838901168ULL,  4702649037537941245ULL,
  14408238429167682374ULL, 17923200330177894118ULL, 7470538549881440849ULL,
  3664543122474851710ULL,  17626200978883719521ULL, 15355649603762884691ULL,
  4749231114166154448ULL,  11220859020615935192ULL, 4740127963151294603ULL,
  16616708905207951068ULL, 9828299274924872726ULL,  8985762004928355786ULL,
  14578866413196595465ULL, 11009044264074492189ULL, 16196760954725621137ULL,
  10725252972011913420ULL, 4601011175737567235ULL,  1441938685024169613ULL,
  1896485105672535586ULL,  6635496128279078494ULL,  7401072902622950072ULL,
  16075245295895555285ULL, 11009539992705810569ULL, 13666961049432909413ULL,
  930044899627839572ULL,   7899294831116079515ULL,  7830402010660588539ULL,
  5485720725031791061ULL,  17051528642209786987ULL, 7280223907880312904ULL,
  10641556535303807158ULL, 12639056541805784436ULL, 12321318600465693220ULL,
  10108223508416203621ULL, 16243972184205577210ULL, 8544062083712081766ULL,
  11274622334580836223ULL, 10844017387984539333ULL, 14774228730866078526ULL,
  560237794062265107ULL,   5844494700804214355ULL,  12270220729021534083ULL,
  8560016492134621125ULL,  12198417933760222474ULL, 10133839346494565561ULL,
  9295901871619786454ULL,  10849442312533122519ULL, 18021432643418872607ULL,
  10155396024449547909ULL, 10524212640889309144ULL, 16662796689072019468ULL,
  965963318619140447ULL,   8887484786999567242ULL,  15714444653107301219ULL,
  1678356452623540647ULL,  11052117692502964420ULL, 14549914962216724919ULL,
  2062106447906584711ULL,  9160372737526136799ULL,  408961132483689555ULL,
  16057982805180036489ULL, 3569128826873655261ULL,  9330490631980133992ULL,
  1176328083272936519ULL,  11222898184704497134ULL, 9302091588024171405ULL,
  10671057562378043302ULL, 4098229850247478874ULL,  8603114141751656125ULL,
  5095034292565071557ULL,  17972196540767155575ULL, 17052421619317624598ULL,
  1582078615100434096ULL,  12012345949788712038ULL, 16161371278263065802ULL,
  2541771182459136706ULL,  4555228648728151989ULL,  8434259952664443907ULL,
  11417314755930316675ULL, 4859944209493970278ULL,  3960064386733120970ULL,
  831798891742765072ULL,   15333350611999607709ULL, 16195235791627584805ULL,
  11597945977924582290ULL, 5623573319924035254ULL,  11517834322140013944ULL,
  4133597640080778846ULL,  5871425684860123605ULL,  1689282515842046354ULL,
  12636468992840026995ULL, 14838814546330146559ULL, 521771145052581487ULL,
  2880434048302248640ULL,  8371131723257691693ULL,  14881811984607317690ULL,
  1324986559026356337ULL,  15096177686518116013ULL, 4421234407032663127ULL,
  14405416956529710514ULL, 3720189381923668652ULL,  409223713688462738ULL,
  9606291214917499037ULL,  9223836018030016969ULL,  190459553092726002ULL,
  12216883190512504355ULL, 2445407445757699168ULL,  4632853494959579227ULL,
  13184809158706083946ULL, 5787237245171889527ULL,  10294885203231741175ULL,
  4191072920233802133ULL,  4291939441266046279ULL,  16375865614446560083ULL,
  8623994097296487259ULL,  15309273767847758202ULL, 9397335507036899909ULL,
  6747046333776906674ULL,  13832845734789247298ULL, 7019441607318179720ULL,
  10005910351872177492ULL, 4145022192145704170ULL,  4353043221960833896ULL,
  8973895156742077167ULL,  438950987149754489ULL,   2185272607213603213ULL,
  8466605802960622962ULL,  12110999198806592422ULL, 11821045514824268224ULL,
  10878266882585355136ULL, 11760743717116988087ULL, 4184976790109698342ULL,
  18330309416210613006ULL, 1107206443001387417ULL,  79384941109554222ULL,
  9163366224008952362ULL,  3321824684344751056ULL,  3693723307432954164ULL,
  6079394558849393056ULL,  11401125038466760935ULL, 3656219353656357222ULL,
  1735342045865967049ULL,  4042759343240967690ULL,  12711975181279962687ULL,
  9500297538285176400ULL,  15298274009373410204ULL, 9806309365986113958ULL,
  10640867530898511005ULL, 17462737140104853956ULL, 4414872795937286161ULL,
  14852747253248972903ULL, 15278706409822090441ULL, 6433625831299907179ULL,
  3321907667985685429ULL,  11390693584827212740ULL, 11529629266037992234ULL,
  10328859824139248147ULL, 16428469301035734767ULL, 17926643922068445985ULL,
  705326063324784242ULL,   8105287564212541268ULL,  15433828269766668455ULL,
  3714790519415313767ULL,  5417718938962187987ULL,  7847045502609209896ULL,
  8025090526912661197ULL,  2234136672994823541ULL,  16041001438425499955ULL,
  10050820915370092068ULL, 14731208739754682952ULL, 9320476318639351023ULL,
  14993011533295358880ULL, 4179632880986595543ULL,  8947621078428360390ULL,
  14715184767037401701ULL, 2617407252848328649ULL,  4818108510694228841ULL,
  3602814087839803186ULL,  14679368779377024657ULL, 7354547195052671772ULL,
  453184876960970470ULL,   15781004944602184656ULL, 12000277437894508493ULL,
  14990587330205222466ULL, 13913588124149397652ULL, 14252160166631667289ULL,
  1532590395334038243ULL,  10283229111568663870ULL, 17325140074534683390ULL,
  15829693190940193580ULL, 7621681592523599724ULL,  10682206684717316020ULL,
  1847393779801417006ULL,  3066262069769536156ULL,  14633662576956154615ULL,
  15324290530255177253ULL, 14627271171597064522ULL, 14334883061544405592ULL,
  12329324284039697670ULL, 14425669906700626239ULL, 4967072546582904838ULL,
  11336784484312139551ULL, 9293117687355182150ULL,  18198595579111618687ULL,
  3236555730692485133ULL,  3659681352365625914ULL,  5185822088933195476ULL,
  1820961806679957133ULL,  5103404090674191862ULL,  16176358349875499548ULL,
  15699479324816269479ULL, 6929077312607579230ULL,  7724671543660786314ULL,
  15226863704421704735ULL, 10411799650043017788ULL, 2743533500235068318ULL,
  7917895244279791454ULL,  9194839772540541837ULL,  8170679394364395846ULL,
  2830213237197365734ULL,  7353896603754987224ULL,  17634372441601249827ULL,
  8515117661105161813ULL,  5818937363197514778ULL,  8536843065945835629ULL,
  2920190566549352463ULL,  4206179361653770600ULL,  15470355568872211976ULL,
  8427825008315838911ULL,  5786540713287383830ULL,  15547153445796060183ULL,
  12329720415526259303ULL, 5557519966701086911ULL
};

TEST(RandomUnitTest, RandomShuffle) {
  Random r;

  const int num_elements = 8;
  const int max_iterations = num_elements * num_elements;

  std::vector<int> previous;
  for (int i = 0; i < num_elements; ++i) {
    previous.push_back(i);
  }

  // Verify that the values have been shuffled
  int count;
  for (count = 0; count < max_iterations; ++count) {
    std::vector<int> copy(previous);
    random_shuffle(copy.begin(), copy.end(), &r);
    if (copy != previous) {
      break;
    }
  }

  ASSERT_NE(count, max_iterations);
}

TEST(RandomUnitTest, RandomSeed) {
  const int max_iterations = 10;
  uint64_t previous = 0;

  // Verify that we get at least 2 unique values
  for (int i = 0; i < 2; ++i) {
    int count;
    // Keep trying while seed equals previous value
    for (count = 0; count < max_iterations; ++count) {
      uint64_t seed = get_random_seed(previous);
      if (seed != previous) {
        previous = seed;
        break;
      }
    }
    ASSERT_NE(count, max_iterations);
  }
}

TEST(RandomUnitTest, MT19937_64) {
  MT19937_64 ng;

  for (int i = 0; i < 626; ++i) {
    uint64_t v = ng();
    EXPECT_EQ(v, random_numbers[i]);
  }
}
